/* 

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。


示例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
*/

/* 
思路1：找出前多少项的和（包括当前项）与当前项比较，取较大值，再用这个最大值与之前存的最大值比较，取较大值
*/

/**
 * @param {number[]} nums
 * @return {number}
 */
//  var maxSubArray = function(nums) {
//     let pre=0,maxNums=nums[0]
//     nums.forEach(x=>{
//         // pre要么取前多少项，要么取当前项，取当前项时即从当前项开始累加
//         pre=Math.max(pre+x,x)
//         maxNums=Math.max(pre,maxNums)
//     })
//     return maxNums
// };

/* 
时间复杂度：O(n)，其中 n为nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。
*/


/* 
思路2：前多少项的和只要大于0，对于子序和都是有益的，当前多少项的和小于0时，从下一项开始从新累加
每次遍历从之前的最大值和当前累加值中取最大
*/
// 性能更好
var maxSubArray = function (nums) {
    let ans = nums[0];
    let sum = 0;
    for (const num of nums) {
        if (sum > 0) {
            sum += num;
        } else {
            sum = num;
        }
        ans = Math.max(ans, sum);
    }
    return ans;
};
// 运行
let nums = [-2,1,-3,4,-1,2,1,-5,4]
console.log(maxSubArray(nums));
